package com.sheng.leetcode.year2023.month06.day12;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2023/06/12
 * <p>
 * 1483. 树节点的第 K 个祖先<p>
 * <p>
 * 给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，<p>
 * 其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。<p>
 * 树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。<p>
 * 实现 TreeAncestor 类：<p>
 * TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。<p>
 * getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：<p>
 * ["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]<p>
 * [[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]<p>
 * 输出：<p>
 * [null,1,0,-1]<p>
 * 解释：<p>
 * TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);<p>
 * treeAncestor.getKthAncestor(3, 1);  // 返回 1 ，它是 3 的父节点<p>
 * treeAncestor.getKthAncestor(5, 2);  // 返回 0 ，它是 5 的祖父节点<p>
 * treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因为不存在满足要求的祖先节点<p>
 * <p>
 * 提示：<p>
 * 1 <= k <= n <= 5 * 10^4<p>
 * parent[0] == -1 表示编号为 0 的节点是根节点。<p>
 * 对于所有的 0 < i < n ，0 <= parent[i] < n 总成立<p>
 * 0 <= node < n<p>
 * 至多查询 5 * 10^4 次<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/kth-ancestor-of-a-tree-node">1483. 树节点的第 K 个祖先</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1483 {

    @Test
    public void test01() {
        int n = 7;
        int[] parent = {-1, 0, 0, 1, 1, 2, 2};
        TreeAncestor obj = new TreeAncestor(n, parent);
        // 1, 0, -1
        System.out.println(obj.getKthAncestor(3, 1));
        System.out.println(obj.getKthAncestor(5, 2));
        System.out.println(obj.getKthAncestor(6, 3));
    }
}

class TreeAncestor {

    int n;

    int[] parent;

    Map<String, Integer> map;

    private int[][] pa;

    /**
     * 初始化
     *
     * @param n      树上有 n 个节点，按照 0 到 n - 1 编号
     * @param parent parent[i] 是节点 i 的父节点
     */
    public TreeAncestor(int n, int[] parent) {
        map = new HashMap<>();
        this.n = n;
        this.parent = parent;
        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        pa = new int[n][m];
        for (int i = 0; i < n; i++) {
            pa[i][0] = parent[i];
        }
        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                pa[x][i + 1] = p < 0 ? -1 : pa[p][i];
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        int m = 32 - Integer.numberOfLeadingZeros(k); // k 的二进制长度
        for (int i = 0; i < m; i++) {
            if (((k >> i) & 1) > 0) { // k 的二进制从低到高第 i 位是 1
                node = pa[node][i];
                if (node < 0) {
                    break;
                }
            }
        }
        return node;

//        List<String> list = new ArrayList<>();
//        list.add(node + "," + k);
//        while (k > 0) {
//            if (map.containsKey(node + "," + k)) {
//                return map.get(node + "," + k);
//            }
//            if (node == 0) {
//                return -1;
//            }
//            node = parent[node];
//            k--;
//            list.add(node + "," + k);
//        }
//        for (String s : list) {
//            map.put(s, node);
//        }
//        return node;
    }
}

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor obj = new TreeAncestor(n, parent);
 * int param_1 = obj.getKthAncestor(node,k);
 */
